#ifndef BINARYHEAP_H
#define BINARYHEAP_H

#include "NodeList.h"
#include "PriorityQueue.h"
#include <vector>

//MakeHeap, FindMin, Insert, DeleteMin, and DecreaseKey
namespace algo {
  template<typename T>
  class BinaryHeap;

  template<typename T>
  class BinaryHeapNode : public PriorityQueueNode<T>
  {
  public:
    BinaryHeapNode(T key) : key(key) {}

    T getKey() const { return key; }

  private:
    friend class BinaryHeap<T>;
    T key;
    size_t index;
  };

  template<typename T>
  class BinaryHeap : public PriorityQueue<T>
  {
  public:
    BinaryHeap() : PriorityQueue<T>("BinaryHeap") {}

    BinaryHeapNode<T> *getMin() const {
      if (!nodes.size())
        return 0;

      return nodes[0];
    }

    BinaryHeapNode<T> *insert(T key) {
      BinaryHeapNode<T> *node = new BinaryHeapNode<T>(key);

      node->index = nodes.size();
      nodes.push_back(node);

      bubbleUp(nodes.size() - 1);

      return node;
    }

    T deleteMin() {
      if (!nodes.size())
        return T();

      T minKey = nodes[0]->key;

      delete nodes[0];

      nodes[0] = nodes.back();
      nodes.pop_back();

      bubbleDown(0);

      return minKey;
    }

    void decreaseKey(PriorityQueueNode<T> *node, T newKey) {
      decreaseKey(static_cast<BinaryHeapNode<T> *>(node), newKey);
    }

    void decreaseKey(BinaryHeapNode<T> *node, T newKey) {
      node->key = newKey;

      bubbleUp(node->index);
    }

    void deleteNode(PriorityQueueNode<T> *node) {
      deleteNode(static_cast<BinaryHeapNode<T> *>(node));
    }

    void deleteNode(BinaryHeapNode<T> *node) {
      decreaseKey(node, 0);
      deleteMin();
    }

  private:
    void bubbleUp(size_t i) {
      if (i <= 0)
        return;

      int parent = (i - 2 + (i % 2)) / 2;

      if (nodes[parent]->key <= nodes[i]->key)
        return;

      custom_count++;
      nodes[i]->index = parent;
      nodes[parent]->index = i;
      std::swap(nodes[i], nodes[parent]);

      bubbleUp(parent);
    }

    void bubbleDown(size_t i) {
      size_t l = 2 * i + 1,
             r = 2 * i + 2;

      int small_child;

      if (l >= nodes.size())
        return;

      if (r >= nodes.size())
        small_child = l;
      else {
        if (nodes[r]->key < nodes[l]->key)
          small_child = r;
        else
          small_child = l;
      }

      if (nodes[i]->key <= nodes[small_child]->key)
        return;

      nodes[i]->index = small_child;
      nodes[small_child]->index = i;
      std::swap(nodes[small_child], nodes[i]);
      bubbleDown(small_child);
    }

    std::vector<BinaryHeapNode<T>*> nodes;
  };
}

#endif //BINARYHEAP_H
